package leetcode.editor.vip.solution651;

// 题目描述：https://labuladong.gitee.io/algo/3/28/94/
public class Solution651 {
    public int maxA(int N) {
        // 定义：dp[i] 表示 i 次操作后最多能显示多少个 A
        int[] dp = new int[N + 1];
        dp[0] = 0;
        for (int i = 1; i <= N; i++) {
            // 直接打印A
            dp[i] = dp[i - 1] + 1;
            // 选择不同位置进行CV，取出最大的
            for (int j = 2; j < i; j++) {
                // 全选 & 复制 dp[j-2]，连续粘贴 i - j 次
                // 屏幕上共 dp[j - 2] * (i - j + 1) 个 A
                // j - 2是为了给 C+A C+C留下空间，才能使用C+V
                dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));
            }
        }

        // N 次按键之后最多有几个 A？
        return dp[N];
    }
}
